package sort;

import java.util.Arrays;

import static tools.Swap.swap;

public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {3, 1, 2, 5, 4};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void heapSort(int[] arr) {

        if (arr == null || arr.length < 2) {
            return;
        }
        int heapSize = arr.length;
      /*  for(int i = 0; i < arr.length; i++) {
            heapInsert(arr,i);
        }*/
        for(int i = arr.length - 1; i >=0;i--){
            heapify2(arr, i, heapSize);
        }
        while(heapSize > 0) {
            swap(arr,0,--heapSize);
            heapify2(arr,0,heapSize);
        }

    }
    public static void heapInsert(int[] arr,int index){
        int parent = (index - 1) / 2;
        while(arr[parent]<arr[index]){
            swap(arr,parent,index);
            index = parent;
            parent = (index - 1) / 2;
        }
    }
    public static void heapify(int[] arr,int index,int heapSize){
        int left=index*2+1;
        while(left<heapSize){
            int right=index*2+2;
            int largest = right<heapSize&&arr[right]>arr[left]?right : left;
            largest = arr[largest] > arr[index] ? largest : index;
            if(largest==index){
                break;
            }
            swap(arr,index,largest);
            index = largest;
            left = index * 2 + 1;
        }
    }
    public static void heapify2(int[] arr,int index, int heapSize){
        int left = index * 2 + 1;
        while(left < heapSize){
            int min = left + 1 < heapSize && arr[left + 1] < arr[left] ? left + 1 : left;
            min = arr[min] < arr[index] ? min : index;
            if(min == index){
                break;
            }
            swap(arr,index,min);
            index = min;
            left = index * 2 + 1;
        }
    }
}
